package com.liang.leetcode.string;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 151. 反转字符串中的单词
 *  给你一个字符串 s ，请你反转字符串中 单词 的顺序。
 *  单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
 *  返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
 *  注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
 *
 * 示例 1：
 * 输入：s = "the sky is blue"
 * 输出："blue is sky the"
 * 示例 2：
 *  输入：s = "  hello world  "
 *  输出："world hello"
 *  解释：反转后的字符串中不能存在前导空格和尾随空格。
 * 示例 3：
 *  输入：s = "a good   example"
 *  输出："example good a"
 *  解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
 *
 */
public class String03_ReverseWords {
    public static void main(String[] args) {
        String words = " the  sky  is blue ";
        words = reverseWords3(words);
        System.out.println(words);
    }

    /**
     * 初步实现，待优化
     */
    public static String reverseWords(String s) {
        // 移除首尾空白字符，并按空格分割成单词数组。
        String[] words = s.trim().split("\\s+");
        // 反转数组内的单词位置
        int i = 0;
        int j = words.length - 1;
        while (i <= j) {
            String temp = words[i];
            words[i] = words[j];
            words[j] = temp;
            i++;
            j--;
        }
        // 将反转后的单词数组合并成一个字符串，单词间以单空格分隔
        StringBuilder sb = new StringBuilder();
        for (String word : words) {
            sb.append(word).append(" ");
        }
        // 移除首尾可能多余的空格并返回结果
        return sb.toString().trim();
    }

    /**
     * 方法一：使用 Java 内置方法实现
     */
    public static String reverseWords2(String s) {
        // 去除首位空格
        s = s.trim();
        // 按照空格分割成字符串数组
        String[] split = s.split("\\s+");
        // 字符数组转为列表
        List<String> wordList = Arrays.asList(split);
        // 翻转字符串列表
        Collections.reverse(wordList);
        // 将列表拼接成字符串
        return String.join(" ", wordList);
    }


    /**
     * 方法二：不使用Java内置方法实现，自行实现
     *  1.去除首尾以及中间多余空格
     *  2.反转整个字符串
     *  3.反转各个单词
     */
    public static String reverseWords3(String s) {
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeExtraSpaces(s);
        System.out.println(sb);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        System.out.println(sb);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    /**
     * 用 StringBuilder 进行优化
     * 1.去除首尾以及中间多余空格
     * " the sky  is  blue "
     */
    public static StringBuilder removeExtraSpaces(String s) {
        int start = 0;
        int end = s.length() - 1;
        // 去除首尾空格
        while (s.charAt(start) == ' ') {
            start++;
        }
        while (s.charAt(end) == ' ') {
            end--;
        }
        // 保存单词，单词之间用空格隔开
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            // 从头开始判断字符，并追加到sb中
            char c = s.charAt(start);
            // 若当前字符c不是空格，或者 sb 的最后一个字符不是空格即不能连续是空格（sb 是动态变化的），则保存该字符
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                // c 可以是字符或者空格
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    /**
     * 2.反转整个字符串
     */
    public static void reverseString(StringBuilder sb, int i, int j) {
        while (i < j) {
            char temp = sb.charAt(i);
            sb.setCharAt(i, sb.charAt(j));
            sb.setCharAt(j, temp);
            i++;
            j--;
        }
    }

    /**
     * 3.反转各个单词
     * 关键在于找到每个单词的开始和结束下标，末尾字符需要单独判断
     */
    public static void reverseEachWord(StringBuilder sb) {
        int start = 0;
        for (int i = 0; i < sb.length(); i++) {
            // 遇到空格，或者是最后一个字符，则找到单词分界点
            if (sb.charAt(i) == ' ' || i == sb.length() - 1) {
                int end = (i == sb.length() - 1) ? i : i - 1;
                reverseString(sb, start, end);
                start = i + 1;
            }
        }
    }
}